// -----------------------------------------------------------------------------
//
//  Author : 	Duke Zhou
//  Data : 		2016/7/28
//
// -----------------------------------------------------------------------------
//

using System;
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using UnityEditor;
using System.Text;

namespace Jelly.Editor.AssetBundle
{
    /// <summary>
    /// 把资源的依赖关系用单向图表示，初始节点（第一层节点、根节点）是不被依赖的可加载资源
    /// 相关资源合并到同一个节点里，共用资源成为单独节点，解决重复冗余问题，并减少bundle数量
    /// </summary>
    [System.Serializable]
    internal class ResGraph
    {
        /// <summary>
        /// 包节点，即会被Load的节点，节点之间可能也会相互依赖
        /// </summary>
        public List<ResNode2> rootNodeList = new List<ResNode2>();
        /// <summary>
        /// 所有用到的Asset节点
        /// </summary>
        public Dictionary<string, ResNode2> allNode = new Dictionary<string, ResNode2>();
        /// <summary>
        /// GroupNodes()之后，表示所有AB包节点
        /// </summary>
        public Dictionary<string, ResNode2> groupedNode;
        
        /// <summary>
        /// GroupNodes()之后，表示最底层依赖的节点，即不依赖其他节点的节点。
        /// </summary>
        public List<ResNode2> tailNodeList = new List<ResNode2>();
        
        // private string[] pathParams = new string[1];
        

        private List<string> tempNodeList = new List<string>();

        private HashSet<string> _forceSingleBundleSet = new HashSet<string>();

        public ResGraph(Dictionary<string, string[]> edgeMap, HashSet<string> forceSingleBundleSet, 
            Dictionary<string, string[]> allAssetFixedDepMap)
        {
            _forceSingleBundleSet = forceSingleBundleSet;
            var iter = edgeMap.GetEnumerator();
            while (iter.MoveNext())
            {
                string path = iter.Current.Key;
                ResNode2 node;
                GenerateResNodeMap(path, iter.Current.Value, allNode, allAssetFixedDepMap, out node);
                CompressNode(node);
                node.isRoot = true;
                rootNodeList.Add(node);
            }
            UpdateReverseDependence();

            if (false)
            {
                tempNodeList.Clear();
                for(int i = 0; i < rootNodeList.Count; ++i)
                {
                    TempLoopByRoot(rootNodeList[i]);
                }
                tempNodeList.Sort();
                StringBuilder sb = new StringBuilder();
                for(int i = 0; i < tempNodeList.Count; ++i)
                {
                    sb.AppendLine(tempNodeList[i]);
                }
                Debug.Log(sb);
                
                sb.Length = 0;
                List<string> allNodeKeyList = new List<string>(allNode.Keys);
                allNodeKeyList.Sort();
                var iter2 = allNodeKeyList.GetEnumerator();
                while(iter2.MoveNext())
                {
                    sb.AppendLine(iter2.Current);
                }
                Debug.Log(sb);
            }
        }

        private void TempLoopByRoot(ResNode2 node)
        {
            if(!tempNodeList.Contains(node.path))
                tempNodeList.Add(node.path);
            int count = node.dependence != null ? node.dependence.Count : 0;
            for(int i = 0; i < count; ++i)
            {
                TempLoopByRoot(node.dependence[i]);
            }
        }

        private void TempLoopByTail(ResNode2 node)
        {
            if(!tempNodeList.Contains(node.path))
                tempNodeList.Add(node.path);
            int count = node.whoDependOnMe != null ? node.whoDependOnMe.Count : 0;
            for(int i = 0; i < count; ++i)
            {
                TempLoopByTail(node.whoDependOnMe[i]);
            }
        }

        
        /// <summary>
        /// 把原始的Path和Path之间的依赖关系生成为ResNode字典
        /// </summary>
        private void GenerateResNodeMap(string path, string[] dependAssets, Dictionary<string, ResNode2> nodeMap, 
                Dictionary<string, string[]> allAssetFixedDepMap, out ResNode2 node)
        {
            if (nodeMap.TryGetValue(path, out node))
                return;
            
            node = new ResNode2(path);
            nodeMap.Add(path, node);
            int count = dependAssets == null ? 0 : dependAssets.Length;
            for (int i = 0; i < count; ++i)
            {
                var dep = dependAssets[i];
                if (dep != path)
                {
                    if (!allAssetFixedDepMap.TryGetValue(dep, out var childDependAssets))
                    {
                        throw new Exception($"{dep} not Exist in loadablePathFixedDepMap");
                    }
                    // pathParams [0] = dep;
                    ResNode2 child;
                    GenerateResNodeMap(dep, childDependAssets, nodeMap, allAssetFixedDepMap, out child);
                    node.originDependence = node.originDependence ?? new List<ResNode2>();
                    node.originDependence.Add(child);
                }
            }
        }
        
        /// <summary>
        /// 如果本节点的依赖中还有相互的依赖，那么可以压缩合并成精简的形式
        /// 原本的依赖是全依赖（originDependence），经过CompressNode处理后，dependence里存放的是压缩后的依赖，即树状依赖
        /// 检查Node的所有子节点，如果某个子节点不是其他某个“子节点”的子节点，则把这个子节点加入到压缩子节点列表。
        /// </summary>
        private void CompressNode(ResNode2 node)
        {
            if (node.compressed)
            {
                return;
            }
            Queue<ResNode2> queue = new Queue<ResNode2>();
            List<ResNode2> recordList = new List<ResNode2>();
            queue.Enqueue(node);
            while (queue.Count > 0)
            {
                node = queue.Dequeue();
                if (node.compressed)
                {
                    continue;
                }
                recordList.Add(node);
                int count = node.originDependence == null ? 0 : node.originDependence.Count;
                for (int i = 0; i < count; ++i)
                {
                    ResNode2 childI = node.originDependence [i];
                    //查找节点I是否是某个子节点的子节点
                    bool dependByOtherChild = false;
                    for (int j = 0; j < count && !dependByOtherChild; ++j)
                    {
                        ResNode2 childJ = node.originDependence [j];
                        if (i != j && childJ.originDependence != null && childJ.originDependence.Contains(childI))
                        {
                            dependByOtherChild = true;
                        }
                    }
                    //如果找到，说明要删除这条路径，就不处理；没找到，说明路径要保留，加入到dependence列表。
                    if (!dependByOtherChild)
                    {
                        //如果I节点有子节点，则再把I当作根节点来遍历
                        if (childI.originDependence != null && childI.originDependence.Count > 0)
                        {
                            queue.Enqueue(childI);
                        } else
                        {
                            recordList.Add(childI);
                        }
                        node.dependence = node.dependence ?? new List<ResNode2>();
						if (!node.dependence.Contains(childI))
						{
							node.dependence.Add(childI);
						}
                    }
                    // 我直接依赖这个dep，其他dep也依赖这个dep，归入其他dep，但要显示设置其assetName到bundle中
                    else if (node.originDirectDep.Contains(childI.path))
                    {
                        childI.whoOriginDirectDependOnMe.Add(node);
                    }
                }
            }
            int recordNum = recordList.Count;
            for (int i = 0; i < recordNum; ++i)
            {
                recordList [i].compressed = true;
            }
        }
       
        /// <summary>
        /// 合并相关资源到同一个bundle里，共用资源独立为单独bundle，解决重复冗余问题
        /// 
        /// 遍历查找只被一个节点依赖的节点，即X、Y、D、E、G、H，然后把该节点归并到父节点的group属性里，
        /// 删除这条路径，并把该节点的所有依赖赋给父节点（剔除重复的），
        /// 如果合并了子节点，则还要再次遍历新的子节点(Z也会合并)
        ///       A -> B <- C     E <- F -> G -> H
        ///            ↓
        ///  Z <- X <- D -> Y -> Z
        /// </summary>
        public void GroupNodes()
        {
//            Debug.Log("GroupNodes");
            groupedNode = new Dictionary<string, ResNode2>(allNode);
            
            int rootCount = rootNodeList.Count;
            for (int i = 0; i < rootCount; ++i)
            {
                ResNode2 node = rootNodeList [i];
                GroupNode(node);
            }
            UpdateTailNodeList();

            if (false)
            {
                tempNodeList.Clear();
                for(int i = 0; i < rootNodeList.Count; ++i)
                {
                    TempLoopByRoot(rootNodeList[i]);
                }
                tempNodeList.Sort();
                StringBuilder sb = new StringBuilder();
                for(int i = 0; i < tempNodeList.Count; ++i)
                {
                    sb.AppendLine(tempNodeList[i]);
                }
                Debug.Log(sb);

                tempNodeList.Clear();
                for(int i = 0; i < tailNodeList.Count; ++i)
                {
                    TempLoopByTail(tailNodeList[i]);
                }
                tempNodeList.Sort();
                sb.Length = 0;
                for(int i = 0; i < tempNodeList.Count; ++i)
                {
                    sb.AppendLine(tempNodeList[i]);
                }
                Debug.Log(sb);

                sb.Length = 0;
                List<string> allNodeKeyList = new List<string>(groupedNode.Keys);
                allNodeKeyList.Sort();
                var iter = allNodeKeyList.GetEnumerator();
                while(iter.MoveNext())
                {
                    sb.AppendLine(iter.Current);
                }
                Debug.Log(sb);
            }
        }
         
        /// <summary>
        /// 递归合并node。如果node只有一个父节点F就合并到F，更新F的依赖包含node的孩子，node的孩子的父节点改为F
        /// </summary>
        /// <returns><c>true</c>, if node was grouped, <c>false</c> otherwise.</returns>
        /// <param name="node">Node.</param>
        private bool GroupNode(ResNode2 node)
        {
            //        Debug.Log("StartGroupNode: " + node.assetName);
            if (node.dependence != null && node.dependence.Count > 0)//还有孩子，则先group孩子节点
            {
                bool groupSomething;
                do
                {
                    groupSomething = false;
                    int count = node.dependence != null ? node.dependence.Count : 0;
                    for (int i = count - 1; i >= 0; --i)//有可能GroupNode之后，node.dependence移除了某个子节点
                    {
                        //                    Debug.Log("------------" + node.dependence[i].assetName);
                        groupSomething |= GroupNode(node.dependence [i]);
                        //                    Debug.Log(groupSomething);
                    }
                // 再来一遍处理新增节点，或这种依赖关系：A->B, A->C, B->D, C->D. 一开始D不能合并到BC，但BC合并到A后，D就能合并到A了
                // 换成宽度优先就不用像现在这样重来了？
                } while(groupSomething);
            }
            if (node.isRoot)//如果是根节点，即会被Load的节点，则不再往上合并
                return false;
            
            //只有一个父节点依赖这个节点且没有强制设置其为一个单独的bundle
            if (node.whoDependOnMe != null && node.whoDependOnMe.Count == 1 && 
                !_forceSingleBundleSet.Contains(node.path))
            {
                ResNode2 parentNode = node.whoDependOnMe [0];
                parentNode.group = parentNode.group ?? new List<ResNode2>();
                parentNode.group.Add(node);
                if (parentNode.dependence != null)//break link to parent
                {
                    parentNode.dependence.Remove(node);
                    node.whoDependOnMe.Remove(parentNode);
                }
                //Loop all child
                int nodeDepCount = node.dependence != null ? node.dependence.Count : 0;
                for (int i = 0; i < nodeDepCount; ++i)
                {
                    ResNode2 childNode = node.dependence [i];
                    childNode.whoDependOnMe.Remove(node);
                    
                    //Link parent && child
                    parentNode.dependence = parentNode.dependence ?? new List<ResNode2>();
                    if (!parentNode.dependence.Contains(childNode))
                    {
                        parentNode.dependence.Add(childNode);
                        
                        if (!childNode.whoDependOnMe.Contains(parentNode))
                        {
                            childNode.whoDependOnMe.Add(parentNode);
                        }
                    }
                }
                
                groupedNode.Remove(node.path);
                return true;
            }
            return false;
        }
        
        private void UpdateTailNodeList()
        {
            tailNodeList.Clear();
            var iter = groupedNode.GetEnumerator();
            while (iter.MoveNext())
            {
                ResNode2 node = iter.Current.Value;
                if (node.dependence == null || node.dependence.Count == 0)
                {
                    tailNodeList.Add(node);
                }
            }
        }

        private void UpdateReverseDependence()
        {
            var iter = allNode.GetEnumerator();
            while (iter.MoveNext())
            {
                ResNode2 node = iter.Current.Value;
                node.whoDependOnMe = node.whoDependOnMe ?? new List<ResNode2>();
                node.whoDependOnMe.Clear();
            }
            
            var iter2 = allNode.GetEnumerator();
            while (iter2.MoveNext())
            {
                ResNode2 node = iter2.Current.Value;
                int dependenceCount = node.dependence != null ? node.dependence.Count : 0;
                for (int i = 0; i < dependenceCount; ++i)
                {
                    ResNode2 depNode = node.dependence [i];
                    if (!depNode.whoDependOnMe.Contains(node))
                    {
                        depNode.whoDependOnMe.Add(node);
                    }
                }
            }
        }
        
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder(2000);
            sb.AppendLine("digraph ResGraph {");
            sb.AppendLine("node [fontsize=20, shape = box];");
            
            var iter = allNode.GetEnumerator();
            while (iter.MoveNext())
            {
                ResNode2 node = iter.Current.Value;
                sb.AppendLine(node.ToString());
            }
            
            sb.AppendLine("}");
            return sb.ToString();
        }

        public string GetGroupedString()
        {
            StringBuilder sb = new StringBuilder(2000);
            sb.AppendLine("digraph ResGraph {");
            sb.AppendLine("node [fontsize=20, shape = box];");
            
            var iter = groupedNode.GetEnumerator();
            while (iter.MoveNext())
            {
                ResNode2 node = iter.Current.Value;
                sb.AppendLine(node.ToString());
            }
            
            sb.AppendLine("}");
            return sb.ToString();
        }
    }
}